package Midium;

/*
 * 2.两数相加
 * 错误思路：先把两个链表转换成两个数，然后相加。  老实人报错：超出int限制，你换成ulong也顶不住
 * 正确思路：直接对应位数相加，如果有进位则在next对应的结点额外+1；注意两个字符串长度不同
 * */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

//错误解法
//public class Solution2 {
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        int sum = 0;
//        int sum1 = 0;
//        int sum2 = 0;
//        int i =1;
//        while (l1.next != null) {
//            sum1 += l1.val*i;
//            i*=10;
//            l1 = l1.next;
//        }
//        sum1+=l1.val*i;
//        i=1;
//        while (l2.next != null) {
//            sum2 += l2.val*i;
//            i*=10;
//            l2 = l2.next;
//        }
//        sum2+=l2.val*i;
//        sum = sum1 + sum2;
//        System.out.println(sum);
//        if (sum / 10 == 0) {
//            return new ListNode(sum, null);
//        }
//        ListNode listNode = new ListNode(sum % 10, null);
//        ListNode p = listNode;
//        while (sum / 10 != 0) {
//            sum /= 10;
//            p.next = new ListNode(sum % 10, null);
//            p = p.next;
//        }
//        return listNode;
//    }
//
//}
public class Solution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode();
        int k = 0;//k表示进位
        int c;
        ListNode p = resultNode;// p表示当前指针
        while (l1 != null || l2 != null || k != 0) {
            c = 0;
            if (l1 != null) {
                c += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                c += l2.val;
                l2 = l2.next;
            }
            c += k;
            if (c / 10 > 0)
                k = 1;
            else
                k = 0;
            p.val = c % 10; //比如5+8等于13，则第一位存3，此时k=1表示进位
            p.next = new ListNode();
            if (l1 == null && l2 == null && k == 0) //注意，结束的时候不要再初始化了
                p.next = null;
            p = p.next;

        }
        return resultNode;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(9, null);
        ListNode b = new ListNode(1, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))))))))));
        Solution2 s2 = new Solution2();
        ListNode listNode = s2.addTwoNumbers(a, b);
        System.out.println(listNode.val + " " + listNode.next.val + " " + listNode.next.next.val + " " + listNode.next.next.next.val);
    }
}